/**
 * 面试题22：链表中倒数第k个节点
 */
public class Offer_22 {
    /**
     * 方法二：前后指针一次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        // 前后指针
        ListNode former = head, latter = head;
        // 前指针先走 k 步
        for (int i = 0; i < k; i++) {
            if (former == null) {
                return null;
            }
            former = former.next;
        }
        // 两个指针一起走
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }

    /**
     * 方法一：两次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode getKthFromEnd1(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        // 计算链表节点数 size
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        // 如果 k > size，那么倒数第 k 个节点不存在
        if (k > size) {
            return null;
        }

        cur = head;
        for (int i = 0; i < size - k; i++) {
            cur = cur.next;
        }
        return cur;
    }

    public static void main(String[] args) {
        // 构造链表
        // 虚拟头节点
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        for (int i = 1; i < 10; i++) {
            cur.next = new ListNode();
            cur.next.val = i;
            cur = cur.next;
        }
        // 打印链表
        cur = dummyHead;
        printListNode(cur.next);

        // 获取链表中倒数第k个节点
        Offer_22 solution = new Offer_22();
        ListNode ans = solution.getKthFromEnd(dummyHead.next, 3);
        // 打印结果
        printListNode(ans);
    }

    public static void printListNode(ListNode node) {
        System.out.print("[");
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.println("null]");
    }
}
